package _动态规划系列._股票买卖问题;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/31 20:05
 * <p>
 * 功能描述:
 */
public class Summary_0188 {

    /**
     * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-w-5/
     * 几道评论蛮好
     * 1.K倒序是为了优化成2维数组，你写3维就没必要倒序了，反而不好理解。
     * 2.至多进行了k次交易时所获得的最大利润
     *
     * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/zhuang-tai-ya-suo-shi-guan-yu-kshi-fou-dao-xu-yao-/
     * 上面是关于k为何倒序的文章，先不看，没时间。
     */
    public int maxProfit(int k,int[] prices) {

        if (prices.length <= 1)
            return 0;
        int maxK = k, n = prices.length;

        if (k > n / 2)
            return maxProfit_inf(prices);

        int[][][] dp = new int[n][maxK + 1][2];

        for (int i = 0; i < n; i++) {
            for (int myk = maxK; myk >= 1; myk--) { //
                if (i - 1 == -1) {

                    dp[0][myk][0] = 0;

                    dp[0][myk][1] = -prices[0];
                    continue;
                }

                dp[i][myk][0] = Math.max(dp[i - 1][myk][0], dp[i - 1][myk][1] + prices[i]);
                dp[i][myk][1] = Math.max(dp[i - 1][myk][1], dp[i - 1][myk - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][maxK][0];
    }

    public int maxProfit_inf(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        if (n == 0) return 0;

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }

}
